/*
 * @Author: szx
 * @Date: 2022-02-17 12:44:11
 * @LastEditTime: 2022-02-17 13:23:27
 * @Description:
 * @FilePath: \leetcode\600-699\688\688.js
 */
/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function (n, k, row, col) {
    const dirs = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];
    const dp = new Array(k + 1).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(0)));
    for (let step = 0; step <= k; step++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (step == 0) dp[0][i][j] = 1;
                else {
                    for (let dir of dirs) {
                        const ni = i - dir[0],
                            nj = j - dir[1];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][col];
};

var knightProbability = function (n, k, row, col) {
    // const dirs = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];
    const dirs = [
        [-2, -1],
        [-2, 1],
        [2, -1],
        [2, 1],
        [-1, -2],
        [-1, 2],
        [1, -2],
        [1, 2]
    ];

    let dp;
    let res = new Array(n).fill(1).map(() => new Array(n).fill(1));
    for (let step = 0; step <= k; step++) {
        dp = res;
        res = new Array(n).fill(0).map(() => new Array(n).fill(0));
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                for (let dir of dirs) {
                    const ni = i - dir[0],
                        nj = j - dir[1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                        res[i][j] += dp[ni][nj] / 8;
                    }
                }
            }
        }
    }
    return res[row][col];
};
